package dp.multi;

import java.util.Arrays;

public class Solution_1143 {

    int[][] memo;

    public int longestCommonSubsequence(String text1, String text2) {
        char[] arr1 = text1.toCharArray();
        char[] arr2 = text2.toCharArray();
        int m = arr1.length;
        int n = arr2.length;
        memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(arr1, arr2, m - 1, n - 1);
    }

    private int dfs(char[] arr1, char[] arr2, int i, int j) {
        if (i < 0 || j < 0)
            return 0;
        if (memo[i][j] != -1)
            return memo[i][j];
        if (arr1[i]==arr2[j])
            return dfs(arr1,arr2,i-1,j-1)+1;
        return memo[i][j]=Math.max(dfs(arr1,arr2,i-1,j),dfs(arr1,arr2,i,j-1));
    }
}
